题目分析
计算器这个题目是经典的栈问题,在学习数据结构时,堆栈的重要应用场景就是实现复杂的数学运算。
栈
在本题没有括号的情况下,出现符号时记录运算操作,出现数字时,查看运算操作,如果是乘除法,则优先级最高,需要立即运算,因此从栈中弹出栈顶元素,与该数字进行操作,并将运算的结果作为新数字压入栈中。如果是加法则直接入栈,如果是减法则取相反数后入栈。最后按照顺序将栈中的所有元素相加即可。
算法的**时间复杂度为$O(n)$,空间复杂度为$O(n)$**。
1 | #include<iostream> |
刷题总结
栈类型的题目是非常经典的,栈也是应用非常广泛的数据结构,在笔试面试中都经常出现,希望大家能够注意类似的题目。